//class Solution {
//public:
//    int lengthOfLIS(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> memo(n);
//        int ret = 0;
//        for (int i = 0; i < n; i++)
//            ret = max(ret, dfs(nums, i, memo));
//        return ret;
//    }
//
//    int dfs(vector<int>& nums, int pos, vector<int>& memo)
//    {
//        if (memo[pos] != 0)
//            return memo[pos];
//
//        int ret = 1;
//        for (int i = pos + 1; i < nums.size(); i++)
//        {
//            if (nums[i] > nums[pos])
//                ret = max(ret, dfs(nums, i, memo) + 1);
//        }
//        memo[pos] = ret;
//        return memo[pos];
//    }
//};





//class Solution {
//public:
//
//    int lengthOfLIS(vector<int>& nums) {
//        int ret = 0, n = nums.size();
//        vector<int> memo(n);
//        for (int i = 0; i < n; i++)
//            ret = max(ret, dfs(nums, memo, i));
//        return ret;
//    }
//
//    int dfs(vector<int>& nums, vector<int>& memo, int pos)
//    {
//        if (memo[pos] != 0) return memo[pos];
//        int ans = 1;
//        for (int i = pos + 1; i < nums.size(); i++)
//        {
//            if (nums[i] > nums[pos])
//            {
//                ans = max(ans, dfs(nums, memo, i) + 1);
//            }
//        }
//        memo[pos] = ans;
//        return memo[pos];
//    }
//};





//class Solution {
//    int memo[201][201];
//public:
//    int getMoneyAmount(int n) {
//        return dfs(1, n);
//    }
//    int dfs(int left, int right)
//    {
//        if (left >= right) return 0;
//        if (memo[left][right] != 0) return memo[left][right];
//        int ret = INT_MAX;
//        for (int head = left; head <= right; head++)
//        {
//            int l = dfs(left, head - 1);
//            int r = dfs(head + 1, right);
//            ret = min(ret, max(l, r) + head);
//        }
//        memo[left][right] = ret;
//        return ret;
//    }
//};



class Solution {
public:
    int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
    int m, n;
    bool vis[201][201];
    int memo[201][201];
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size(), n = matrix[0].size();
        int ret = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                vis[i][j] = true;
                ret = max(ret, dfs(matrix, i, j));
                vis[i][j] = false;
            }
        }
        return ret;
    }

    int dfs(vector<vector<int>>& matrix, int i, int j)
    {
        if (memo[i][j] != 0) return memo[i][j];
        int ret = 1;
        for (int k = 0; k < 4; k++)
        {
            int x = dx[k] + i, y = dy[k] + j;
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j] && !vis[x][y])
            {
                vis[x][y] = true;
                ret = max(ret, dfs(matrix, x, y) + 1);
                vis[x][y] = false;
            }
        }
        memo[i][j] = ret;
        return ret;
    }
};